﻿// 0806train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <limits>

using namespace std;


/*
 一个整数 num 的 k 美丽值定义为 num 中符合以下条件的 子字符串 数目：
- 子字符串长度为 k 。
- 子字符串能整除 num 。
给你整数 num 和 k ，请你返回 num 的 k 美丽值。
注意：
- 允许有 前缀 0 。
- 0 不能整除任何值。
一个 子字符串 是一个字符串里的连续一段字符序列。

示例 1：
输入：num = 240, k = 2
输出：2
解释：以下是 num 里长度为 k 的子字符串：
- "240" 中的 "24" ：24 能整除 240 。
- "240" 中的 "40" ：40 能整除 240 。
所以，k 美丽值为 2 。
示例 2：
输入：num = 430043, k = 2
输出：2
解释：以下是 num 里长度为 k 的子字符串：
- "430043" 中的 "43" ：43 能整除 430043 。
- "430043" 中的 "30" ：30 不能整除 430043 。
- "430043" 中的 "00" ：0 不能整除 430043 。
- "430043" 中的 "04" ：4 不能整除 430043 。
- "430043" 中的 "43" ：43 能整除 430043 。
所以，k 美丽值为 2 。

 */

bool IsTarget01(const string&mini_str, const string&origin_str)
{
    int mini_num = stoi(mini_str);
    int origin_num = stoi(origin_str);

    //被除数不能为0
    if (mini_num == 0) return false;

    if (origin_num % mini_num==0)
    {
        return true;
    }

    return false;
    //------
}

int solve01(int num, int k)
{
    //1 IsTarget01
    //2 num_str.substr(0,limit)
    //3left_index=1,right_index=limit
    //result+=1
    string num_str = to_string(num);
    int limit = k;

    string init_num_str = num_str.substr(0, limit);
    int result = 0;
    if (IsTarget01(init_num_str, num_str))
    {
        result += 1;
    }
    int str_size = num_str.size();
    for (int left_index=1,right_index=limit;right_index< str_size;left_index++,right_index++)
    {
        string mini_str = num_str.substr(left_index, limit);
        if (IsTarget01(mini_str, num_str))
        {
            result += 1;
        }

    }
    return result;
    //solve01
}


/*
 如果一个字符串不含有任何重复字符，我们称这个字符串为 好 字符串。
给你一个字符串 s ，请你返回 s 中长度为 3 的 好子字符串 的数量。
注意，如果相同的好子字符串出现多次，每一次都应该被记入答案之中。
子字符串 是一个字符串中连续的字符序列。
示例 1：
输入：s = "xyzzaz"
输出：1
解释：总共有 4 个长度为 3 的子字符串："xyz"，"yzz"，"zza" 和 "zaz" 。
唯一的长度为 3 的好子字符串是 "xyz" 。
示例 2：
输入：s = "aababcabc"
输出：4
解释：总共有 7 个长度为 3 的子字符串："aab"，"aba"，"bab"，"abc"，"bca"，"cab" 和 "abc" 。
好子字符串包括 "abc"，"bca"，"cab" 和 "abc" 。
 */

bool IsTarget02(string&mini_str)
{
    unordered_set<char>oh_set;

    bool result = true;
    for (auto&oh_char:mini_str)
    {
        if (oh_set.count(oh_char))
        {
            result = false;
        }
        oh_set.insert(oh_char);
    }

    return result;
    //IsTarget02
}

int solve02(string s) {

    //1IsTarget,判断是否非重复
    //2 .substr(0,limit)
    //3 left_index=1,right_index=limit
    //4 result+=1
    string oh_str = s;
    int str_size = s.size();

    if (str_size==1)
    {
        return 0;
    }

    int limit = 3;
    int result = 0;
    string init_str = oh_str.substr(0, limit);

    if (IsTarget02(init_str))
    {
        result += 1;
    }

    for (int left_index=1,right_index=limit; right_index<str_size; left_index++,right_index++)
    {
        string mini_str = oh_str.substr(left_index, limit);

        if (IsTarget02(mini_str))
        {
            result += 1;
        }

        //for------
    }

    return result;
    //countGoodSubstrings
}



/*
 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
 */
bool IsTarget03(unordered_map<char, int>&curr_map, unordered_map<char,int>&target_map)
{
    bool result = true;
    for (auto&map_item: target_map)
    {
        char key = map_item.first;
        if (curr_map[key]!=map_item.second)
        {
            result = false;
            break;
        }

    }
    return result;
    //------
}

vector<int>solve03(string&s, string&p)
{
    string oh_str = s;
    string target_str = p;
    int str_size = oh_str.size();
    int limit = target_str.size();

    vector<int>result_vec;

    unordered_map<char, int>target_map;
    for (auto&oh_char:target_str)
    {
        target_map[oh_char] += 1;
    }

    string init_str = oh_str.substr(0, limit);
    unordered_map<char, int>curr_map;
    for (auto&oh_char:init_str)
    {
        curr_map[oh_char] += 1;
    }

    if (IsTarget03(curr_map,target_map))
    {
        result_vec.push_back(0);
    }

    int prev_index = 0;

    for (int left_index=1,right_index=limit;right_index<str_size; left_index++,right_index++)
    {
        char prev_char = oh_str[prev_index];
        curr_map[prev_char] -= 1;

        char new_char = oh_str[right_index];
        curr_map[new_char] += 1;

        if (IsTarget03(curr_map,target_map))
        {
            result_vec.push_back(left_index);
        }

        //更新！
        prev_index = left_index;
        //for------
    }

    return result_vec;
    //solve03
}

int main()
{
	{
        //s = "cbaebabacd", p = "abc"
        //[0,6]
        string s = "cbaebabacd";
        string p = "abc";
        vector<int>result_vec = solve03(s, p);;
        for (auto&num:result_vec)
        {
            cout << num << ' ';
        }
        return 0;
	}


	{
        //s = "xyzzaz" 1
        //s = "aababcabc" 4

        string s = "aababcabc";
        cout << solve02(s);

        return 0;
	}

	{
        string oh_str = "xyz";
        cout << IsTarget02(oh_str);
        return 0;
	}

    //num = 240, k = 2 2
    //num = 430043, k = 2 2
    int origin_str = 430043;
    int limit = 2;
    cout << solve01(origin_str, limit);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
